// 示例 1：
// 输入：n = 3
// 输出：5
// 示例 2：

// 输入：n = 1
// 输出：1

n = 4

var numTrees = function (n) {
    let dp = new Array(n + 1).fill(0) // n个节点能组成的最多二叉搜索树
    // dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
    // dp[i] += dp[j-1]*dp[i-j]
    dp[0] = 1
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i] += dp[j - 1] * dp[i - j]
        }
    }
    return dp
}

console.log(numTrees(n));
